Compressed data is often read or received as a continuous stream, with discrete segments that must be decompressed as they are read. Under many compression schemes, the segments have variable lengths. Each segment begins with a control word indicating the length of the segment or the number of data bytes or elements that follow the control word.
FIG. 1 shows an example of a data stream 10 having multiple discrete segments 11, referred to as segments A through N. Each segment has a control word or element 12, followed by a variable number of data elements 13. In the example, the control elements are labeled "CONTROL A" through "CONTROL N". The data elements are similarly labeled to correspond to their control elements. For example, the data elements corresponding to control element CONTROL A are labeled "DATA A1" through "DATA A2".
Each control word contains a value indicating, among other things, the number and/or length of the following data elements within the segment. The next control word is located after the indicated number of data elements.
There are various different types of compression schemes that utilize control elements followed by a variable number of data elements. Two specific examples are found in U.S. Pat. Nos. 5,060,286 and 5,452,405, which are hereby incorporated by reference. Note that the control elements might indicate various things about the following data elements in addition to their length, such as for example an offset relative to previous data values.
One characteristic of compressed data streams as shown in FIG. 1 is that they must be read in their normal, forward order, in which control elements precede data elements. Reading the data stream in reverse order is impossible. Suppose, for example, that reading was to begin at the end of data stream 10, at the data element labeled DATA N2. The problem with this is that there would be no way to know the number of data elements preceding the control element labeled 15. Thus, it would be impossible to locate the control element or to differentiate it from data elements.
In spite of the difficulties, it is sometimes required to consume a compressed data stream in reverse order. Bi-directional raster-type printers illustrate the need for such reverse consumption. In printers such as this, multiple printhead passes over a single raster row are often required. The data corresponding to the raster row is needed first in its original order for a first pass of the printhead in a forward direction, and then in reverse order for a second pass of the printhead in a reverse direction.
There are two primary solutions to this problem. The first solution is to modify the compression scheme by placing a similar control element both before and after the data elements of a particular segment. The disadvantage of this solution is that it doubles the number of required control words, thereby reducing the efficiency of the compression scheme.
The second primary solution is to create and hold a copy of the decompressed data during a first, forward decompression of the data stream, and subsequently refer to the decompressed data rather than to the original compressed data stream. The disadvantage of this solution is that it requires significant amounts of memory to store the decompressed data.
The inventors have developed a way to consume compressed data bi-directionally, without decreasing compression efficiency, and without requiring added memory.